1. Field of the Invention
Embodiments of the invention relate to computer vision and three-dimensional (3D) image reconstruction.
2. Description of the Related Art
Over the past twenty years many well documented techniques have been developed in the field of computer vision to try to reconstruct, digitize and track objects in 3D. One such technique is the reconstruction of objects from multiple two-dimensional (2D) outline images captured of this object. This technique typically makes use of a 3D volume of voxels which are carved using the 2D outline images from varying viewpoints. This technique has been effectively used to generate voxel volumes that represent the general 3D shape of the object being reconstructed.
Several algorithms have been published for the computation of the visual hull, including, for example: W. Martin and J. K. Aggarwal, “Volumetric descriptions of objects from multiple views,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 5, no. 2, pp. 150-158, March 1983; M. Potmesil, “Generating octree models of 3D objects from their silhouettes in a sequence of images,” Computer Vision, Graphics and Image Processing, vol. 40, pp. 1-29, 1987; Richard Szeliski, “Rapid octree construction from image sequences,” CYGIP: Image Understanding, vol., 58; no. 1, pp, 23-32, July 1993; and W. Niem, “Robust and Fast Modeling of 3D Natural Objects from Multiple Views”, Proceedings “Image and Video Processing II”, Vol. 2182. pp. 388-397 (1994). The contents of these documents are hereby incorporated by reference herein.
These approaches attempt to solve the problem in a volumetric space representation. The most common of these representations is to subdivide a 3D box into a set of voxels of discrete size. The size of the box is predetermined so that the object can be contained by it. To improve performance these may be represented as “octrees” or are run-length encoded.
Further related information can be found in: C. H. Chien and J. K. Aggarwal, “Identification of 3D Objects from Multiple Silhouettes Using Quadtrees/Octrees”, Computer Vision Graphics And Image Processing 36, pp. 256-273 (1986); and A. W. Fitzgibbon, G. Cross and A. Zissermann, “Automatic 3D Model Construction for Turntable Sequences”, Proceedings of the European Workshop on 3D Structure from Multiple images of Large-scale Environments (SMILE '98), LNCS 1506, pp. 155-170 (1998). The contents of these documents are hereby incorporated by reference herein.
The problem with traditional space carving techniques is one of performance and flexibility. By predefining a 3D grid of voxels, computer resources are quickly depleted. Real-time performance has only been possible with greatly reduced resolutions involving as few as 1 million voxels representing a 100×100×100 low-resolution grid. Many techniques have been developed to try to optimize this approach using space subdivisions and other optimizations. These techniques have helped but have not made a voxel-based approach a real-time practicality. U.S. Pat. No. 7,127,362 describes one such approach. The contents of this patent are hereby incorporated by reference herein.
After image reconstruction using the above techniques, researchers have often used various techniques of analyzing and tracking the objects. Analyzing voxel grids has proven to be very time-intensive. One technique of tracking a human figure represented by a voxel grid has been described in U.S. Pat. No. 7,257,237. The contents of this patent are hereby incorporated by reference herein.
Accordingly, there exists a need in the art for improved systems and methods for 3D image reconstruction.